package algorithm.leetcode.I1to100;

import java.util.Stack;

/**
 * 接雨水
 */

public class Q42 {

    public int trap(int[] height) {
        int sum = 0;
        int maxLeft = 0, maxRight = 0;
        int left = 1, right = height.length - 2;
        for (int i = 1; i < height.length-1; i++) {
            if (height[left-1] < height[right+1]) {
                maxLeft = Math.max(maxLeft, height[left-1]);
                int min = maxLeft;
                if (min > height[left]) sum = sum + (min - height[left]);
                left ++;
            } else {
                maxRight = Math.max(maxRight, height[right+1]);
                int min = maxRight;
                if (min > height[right]) sum = sum + (min - height[right]);
                right --;
            }
        }
        return sum;
    }

    /**
     * 用2个数组分别记录从左到右的最大高度和从右到左的最大高度, 上面的代码是由本代码优化而来
     * 最好理解,空间复杂度稍高
     * @param height
     * @return
     */
    public int trap2(int[] height) {
        int[] left2Right = new int[height.length];
        int[] right2Left = new int[height.length];
        for (int i = 1; i < height.length-1; i++) {
            left2Right[i] = Math.max(left2Right[i-1], height[i-1]);
            right2Left[height.length-i-1] = Math.max(right2Left[height.length-i], height[height.length-i]);
        }

        int sum = 0;
        for (int i = 1; i < height.length-1; i++) {
            sum += Math.max(Math.min(left2Right[i], right2Left[i]) - height[i], 0);
        }
        return sum;
    }

    public int trapByStack(int[] height) {
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        int current = 0;

        while (current < height.length) {
            // 栈不空并且当前指向的高度大于栈顶高度就保持循环
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int h = height[stack.peek()];
                stack.pop();
                if (stack.isEmpty()) break;
                int distance = current - stack.peek() - 1;
                int min = Math.min(height[stack.peek()], height[current]);
                sum = sum + distance * (min - h);
            }
            stack.push(current);
            current ++;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] a = {2,1,0,3,2,1,2,1};
        Q42 ft = new Q42();
        System.out.println(ft.trapByStack(a));
    }

}
